Wireless ad-hoc networks, which are self-organising, rapidly deployable and which require no fixed infra-structure since they are made solely (or at least largely) of self-contained wireless devices, are known and have been the subject of considerable research in recent times. However, such networks as proposed heretofore have been restricted in their approaches to obtaining positional information about individual devices within the network. In the main, three different types of approach have been adopted: approach 1 is simply not to provide positional information about individual devices within the network; approach 2 is to rely on such information being known a priori (eg by having been carefully placed in pre-ordained positions) and not being liable to change in an unpredictable manner; approach 3 is to use devices which include Global Positioning Systems (GPS's). In certain applications for such networks however, none of the above approaches is ideal. For example, in an application for sensing ocean conditions using an ad-hoc network of free floating sensors the first approach is not ideal because the sense data from each sensor is only valuable if accompanied with the position of the sensor at the time the data was recorded; the second approach is not tenable because the sensors will move with the ocean currents in an unpredictable manner (even assuming their initial placement was known); and the third approach is non-ideal because of the expense of supplying each sensor with a GPS.
In “GPS-free positioning in mobile ad hoc networks” by Srdjan Capkun, et al., Cluster Computing, Volume 5, #2, April 2002 the authors describe an algorithm for permitting devices within a wireless ad-hoc network to obtain relative positional information without the use of any GPS containing devices, using only information about the distances between devices in range of one another (which information, it is said, can be found using a Time of Arrival (TOA) or similar range finding method). The paper mentions that the relative positional information could be associated with a geographical coordinate system only “if the algorithm is used along with some GPS-capable devices.” However, it does not mention how this would be done. It also points out that for some applications (of particular concern to the authors) purely relative positional information is sufficient. The main drawback with the proposed method is that it does not scale well to large systems. The number of communications that each node is required to make increases as the number of nodes in the network increases. This means that beyond small networks the time needed and the processor power required becomes restrictive. Additionally, the calculations required of each device to execute the described algorithm are relatively arduous for very simple devices and therefore likely to be costly in terms of power consumption; additionally, the complexity has a negative impact on the speed with which the relative positions of the devices can be recalculated in the event of movement of the devices.
An alternative approach has also been considered in the field of ad-hoc wireless networks which, however, involves the use of base-stations for location purposes. In this approach (which may be thought of as a semi-ad-hoc semi-cellular approach) simple devices are able to communicate with one another to navigate data through the network (rather than just communicating with base stations as in purely cellular systems), but use only the base stations for location determination purposes (ie they do not attempt to determine their location from the locations of neighbouring simple devices only from neighbouring base stations). This approach has the disadvantage that a relatively large number of the more expensive base stations are required throughout the network.
Yet a further alternative approach has been described by Chris Savarese and Jan Rabaey in two recently published papers (SAVARESE C ET AL: “Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks” USENINX TECHNICAL ANNUAL CONFERENCE, PAGES 317–328, MONTEREY, Calif., JUNE 2001, XP002225742; and SAVARESE C ET AL: “Locationing in Distributed Ad-Hoc Wireless Sensor Networks” 2001 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING. PROCEEDINGS (CAT. NO. 01CH37221), SALT LAKE CITY, Utah, USA, 7–11 MAY 2001, pages 2037–2040 vol. 4, XP0022257432001, Piscataway, N.J., USA, IEEE, USA, ISBN: 0-7803-7041-4). These papers describe a sophisticated and robust two stage method for locating devices in a wireless ad-hoc sensor network in which a small proportion only of the devices are position aware (so called anchor nodes, which correspond to the “gps” or “a priori” nodes referred to in this document). The first stage of the algorithm involves a series of communications spreading out from the anchor nodes by which each (non-anchor) node determines how many hops it is removed from each anchor node. An approximate average distance of each hop is then calculated from knowledge of the shortest number of hops between each pair of anchor nodes and the distances between each pair of anchor nodes (eg if anchor nodes A and B have a shortest path between them of 5 hops and are located at positions (0,0) and (0,10) according to some arbitrary but fixed global coordinate system, then each hop can be attributed an average size of 10/5=2 units). By ensuring that there are at least three anchor nodes, and each node knows its shortest path (in terms of number of hops) to each of at least three anchor nodes, it is able to calculate an approximate location for itself. The second stage of the algorithm then iteratively refines these approximate locations by having each node broadcasting its own most recently calculated position to its neighbouring nodes together with a measure of “confidence” (which varies between 1 and 0) in the accuracy of the broadcast position (with anchor nodes having a confidence of 1 and other nodes having an initial confidence of 0.1). Thereafter, non-anchor nodes update their positions by attempting to triangulate from the received broadcast positions of their immediate neighbours from whom they have also determined a range measurement and assign a confidence to their position updated in this manner which is the average of the confidences assigned (and broadcast) by their immediate neighbours. The iterative procedure is repeated a predetermined number of times and then stopped. Nodes which still have a low confidence in their position are disregarded.
Whilst the above described location method of Svarese et al. is quite sophisticated and robust, it would be desirable to provide an improved method which is just as robust but which has improved performance in terms of both the accuracy with which nodes are able to locate themselves and the proportion of nodes which are able to determine their position with a high level of confidence.